The problem of recovering a structured signal $\mathbf{x} \in \mathbb{C}^p$from a set of dimensionality-reduced linear measurements $\mathbf{b} = \mathbf{A}\mathbf {x}$ arises in a variety of applications, such as medical imaging,spectroscopy, Fourier optics, and computerized tomography. Due to computationaland storage complexity or physical constraints imposed by the problem, themeasurement matrix $\mathbf{A} \in \mathbb{C}^{n \times p}$ is often of theform $\mathbf{A} = \mathbf{P}_{\Omega}\boldsymbol{\Psi}$ for some orthonormalbasis matrix $\boldsymbol{\Psi}\in \mathbb{C}^{p \times p}$ and subsamplingoperator $\mathbf{P}_{\Omega}: \mathbb{C}^{p} \rightarrow \mathbb{C}^{n}$ thatselects the rows indexed by $\Omega$. This raises the fundamental question ofhow best to choose the index set $\Omega$ in order to optimize the recoveryperformance. Previous approaches to addressing this question rely onnon-uniform \emph{random} subsampling using application-specific knowledge ofthe structure of $\mathbf{x}$. In this paper, we instead take a principledlearning-based approach in which a \emph{fixed} index set is chosen based on aset of training signals $\mathbf{x}_1,\dotsc,\mathbf{x}_m$. We formulatecombinatorial optimization problems seeking to maximize the energy captured inthese signals in an average-case or worst-case sense, and we show that thesecan be efficiently solved either exactly or approximately via theidentification of modularity and submodularity structures. We provide bothdeterministic and statistical theoretical guarantees showing how the resultingmeasurement matrices perform on signals differing from the training signals,and we provide numerical examples showing our approach to be effective on avariety of data sets.
展开▼
